package Leetcode第一期;

import java.util.*;

/**
 * @author : K k
 * @date : 13:17 2020/9/2
 */
public class 最小的k个数_40 {
    public int[] getLeastNumbers(int[] arr, int k) {
        Arrays.sort(arr);
        int[] ans=new int[k];
        for (int i=0;i<k;i++){
            ans[i]=arr[i];
        }
        return ans;
    }
    //冒泡排
    public int[] getLeastNumbersA(int[] arr, int k) {
        int end=arr.length-1;
        //
        for (int i=end ;i>=0;i--){
            if (end-i==k){break;}
            for (int j=end;j>=end-i+1;j--){
                if (arr[j]<arr[j-1]){
                    //冒泡排序交换
                    swap(arr,j,j-1);
                }
            }
        }
        return Arrays.copyOfRange(arr,0,k);
    }
    //堆排
    public int[] getLeastNumbersB(int[] arr, int k) {
        Set<Integer> set=new TreeSet<>((i1, i2) -> Integer.compare(i2, i1));
        if (k==0 || arr.length==0){return new int[0];}
        //默认是小顶堆，需要实现comparator接口
        Queue<Integer> heap = new PriorityQueue<>(k, (i1, i2) -> Integer.compare(i2, i1));
        for (int element : arr) {
            //若堆不满k 或者比堆中最小的数小
            if (heap.isEmpty() || heap.size() < k || element < heap.peek()) {
                heap.offer(element);
            }
            if (heap.size()>k){
                heap.poll();
            }
        }
        // 将堆中的元素存入数组
        int[] res = new int[heap.size()];
        int j = 0;
        for (int e : heap) {
            res[j++] = e;
        }
        return res;
    }

    //快排
    public int[] getLeastNumbersC(int[] arr, int k) {
        //快排解决
        if (arr==null||arr.length==0){return null;}
        quickSort(arr,0,arr.length-1);
        return Arrays.copyOfRange(arr,0,k);
    }

    private void quickSort(int[] arr, int left, int right) {
        if (left<right){
            int middle=getMiddle(arr,left,right);
            quickSort(arr,left,middle-1);
            quickSort(arr,middle+1,right);
        }

    }

    private int getMiddle(int[] arr, int left, int right) {
        int tmp=arr[left];//基准值
        while (left<right){
            while (left<right && arr[right]>=tmp){
                right--;
            }
            arr[left]=arr[right];
            while (left<right && arr[left]<=tmp){
                left++;
            }
            arr[right]=arr[left];
        }
        arr[left]=tmp;
        return left;
    }

    private void swap(int[] arr, int i, int j) {
        int tmp=arr[j];
        arr[j]=arr[i];
        arr[i]=tmp;
    }

    public static void main(String[] args) {
        最小的k个数_40 x=new 最小的k个数_40();
        int[] leastNumbersA = x.getLeastNumbersB(new int[]{4,3, 2, 1}, 2);
        for (int u :
                leastNumbersA) {
            System.out.println(u);
        }
    }
}
